/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LXW
 * Date: 2022-03-11
 * Time: 13:35
 */
public class Test {
    public void mergeSort(int[] array, int left, int right,int[] temp) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        mergeSort(array,left,mid,temp);
        mergeSort(array,mid+1,right,temp);
        merge(array,left,mid,right,temp);
    }
    public void merge(int[] array,int left,int mid,int right,int[] temp) {
        temp = new int[array.length];
        int i = left;
        int j = mid+1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k] = array[i];
                i++;
                k++;
            }else {
                temp[k] = array[j];
                j++;
                k++;
            }
        }
        while (i <= mid) {
            temp[k] = array[i];
            i++;
            k++;
        }
        while(j <= right) {
            temp[k] = array[j];
            j++;
            k++;
        }
        for (int l = 0; l < temp.length; l++) {
            array[left++] = temp[l]; // 这里注意：array这次拷贝完后，下次再拷贝的时候要从上次拷贝结束的最后一个位置开始
        }
    }
}
